package com.berchen.数据结构.二叉树.赫夫曼编解码;

import java.io.*;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * 赫夫曼压缩
 */
public class HuffmanCode {

    // 赫夫曼树编码
    private Map<Byte,String> huffmanMap=new HashMap<>();
    private StringBuffer stringBuffer=new StringBuffer();


    /**
     * 解压缩文件
     * @param zipFile 需要解压的文件
     * @param mdFile 解压到什么地方
     */
    public void unZipFile(String zipFile,String mdFile){
        OutputStream os=null;
        InputStream is = null;
        ObjectInputStream ois=null;
        try{
            is=new FileInputStream(zipFile);
            ois=new ObjectInputStream(is);

            // 得到压缩后的字节码
            byte[] bytes= (byte[]) ois.readObject();
            // 得到赫夫曼编码
            Map<Byte,String> huffmanMap= (Map<Byte, String>) ois.readObject();

            // 解压缩后得到的字节数组
            byte[] unZip = unZip(bytes, huffmanMap);

            os=new FileOutputStream(mdFile);
            os.write(unZip);
        }catch (Exception e ){
            e.printStackTrace();
        }
        finally {
            try{
                if(is!=null){
                    is.close();
                }
                if(ois!=null){
                    ois.close();
                }
                if(os!=null){
                    os.close();
                }
            }catch (Exception e ){
                e.printStackTrace();
            }
        }
    }

    /**
     * 压缩 文件
     * @param srcFile 原始文件路径
     * @param mdFile    目标文件路径
     */
    public void zipFile(String srcFile,String mdFile){
        OutputStream os=null;
        ObjectOutputStream oos=null;
        InputStream is = null;
        try{

            is=new FileInputStream(srcFile);
            byte[] bytes=new byte[is.available()];
            is.read(bytes);
            // 压缩  得到压缩后的字节数组
            byte[] zip = zip(bytes);

            os=new FileOutputStream(mdFile);
            oos=new ObjectOutputStream(os);

            // 写到新文件中
            oos.writeObject(zip);   // 在解码打时候好读取
            oos.writeObject(huffmanMap); // 在解码的时候好读取
        }catch (Exception e ){
            e.printStackTrace();
        }
        finally {
            try{
                if(is!=null){
                    is.close();
                }
                if(oos!=null){
                    oos.close();
                }
                if(os!=null){
                    os.close();
                }
            }catch (Exception e ){
                e.printStackTrace();
            }
        }
    }



    /**
     * 解压缩
     * @param bytes
     * @return
     */
    public byte[] unZip(byte[] bytes){

        return unZip(bytes,huffmanMap);
    }
    /**
     * 解压缩
     * @param bytes 要解压缩的字节数组
     * @return
     */
    private byte[] unZip(byte[] bytes,Map<Byte,String> map){
        // 将map打key和value 互换
        Map<String,Byte> fanMap=new HashMap<>();
        for(Map.Entry<Byte,String> entry:map.entrySet()){
            fanMap.put(entry.getValue(),entry.getKey());
        }

        // 将要解压打字节数组 变成字符串 010100101001
        StringBuffer stringBuffer=new StringBuffer();
        for(int i =0;i<bytes.length;i++){
            stringBuffer.append(byteToBitStr(!(i== bytes.length-1),bytes[i]));
        }

        List<Byte> resultList=new ArrayList<>();
        StringBuffer sb2=new StringBuffer();
        Byte b=null;
        // 解压缩
        for(int i =0;i<stringBuffer.length();i++){
            sb2.append(stringBuffer.substring(i,i+1));
            b = fanMap.get(sb2.toString());
            if(b==null){
                continue;
            }
            else {
                resultList.add(b);
                sb2.delete(0,sb2.length());
            }
        }

        byte[] resultByte=new byte[resultList.size()];
        for(int i =0;i<resultList.size();i++){
            resultByte[i]=resultList.get(i);
        }
        return  resultByte;
    }

    /**
     * 将一个byte 转成一个二进制打字符串
     * @param falg 是否需要补高位
     * @param b
     * @return
     */
    private String byteToBitStr(boolean falg,byte b){

        int temp=b;
        if(falg){
            temp|=256;
        }
        String str=Integer.toBinaryString(temp);
        return falg?str.substring(str.length()-8):str;
    }

    /**
     * 压缩
     * @param bytes
     * @return
     */
    public byte[] zip(byte[] bytes){
        getHuffmanMap(getHuffmanTree(getHuffmanNodes(bytes)));
        return zip(bytes,huffmanMap);
    }
    /**
     * 压缩
     * @param bytes 要压缩的字节数组
     * @param map   赫夫曼编码 用这个来进行压缩
     * @return
     */
    private byte[] zip(byte[] bytes,Map<Byte,String> map){

        // 将 byte转换成  010100101010100101001的二进制
        StringBuffer stringBuffer=new StringBuffer();
        for(int i =0;i<bytes.length;i++){
            stringBuffer.append(map.get(bytes[i]));
        }

        // 存储压缩后的字节数组
        byte[] resultByte=new byte[(stringBuffer.length()+7)/8];
        int index=0;
        String strByte="";
        // 以8 位作为一个byte
        for(int i =0;i<stringBuffer.length();i+=8){
            if(i+8<=stringBuffer.length()){
                strByte=stringBuffer.substring(i,i+8);
            }
            else {
                strByte=stringBuffer.substring(i);
            }
            resultByte[index++]= (byte) Integer.parseInt(strByte,2);
        }
        return resultByte;
    }

    /**
     * 生成赫夫曼编码
     * @param root
     * @return
     */
    public void getHuffmanMap(HuffmanNode root){

        if(root==null){
            return;
        }
        getHuffmanMap(root,"",stringBuffer);
    }
    private void getHuffmanMap(HuffmanNode node,String code,StringBuffer sb){

        StringBuffer sb1=new StringBuffer(sb);
        sb1.append(code);
        if(node!=null){
            if(node.data==null){    // 判断是否是叶子节点
                getHuffmanMap(node.left,"0",sb1);
                getHuffmanMap(node.right,"1",sb1);
            }else {
                huffmanMap.put(node.data,sb1.toString());
            }
        }
    }

    /**
     * 生成赫夫曼树
     * @param nodes
     * @return
     */
    public HuffmanNode getHuffmanTree(List<HuffmanNode > nodes){

        if(nodes==null||nodes.size()<=0){
            return null;
        }
        while (nodes.size()>=2){

            HuffmanNode left=nodes.get(0);
            HuffmanNode right=nodes.get(1);

            HuffmanNode root=new HuffmanNode(null,left.weight+ right.weight);
            root.left=left;
            root.right=right;

            nodes.remove(left);
            nodes.remove(right);

            nodes.add(root);
        }
        return nodes.get(0);
    }
    /**
     * 将 字节数组  变成List<HuffmanNode>用于生成赫夫曼树</>
     * @param bytes
     * @return
     */
    public List<HuffmanNode> getHuffmanNodes(byte[] bytes){

        Map<Byte,Integer> map=new HashMap<>();  // 用来保存 每个字符出现的次数
        for(int i =0;i<bytes.length;i++){
            Integer count=map.get(bytes[i]);
            if (count == null) {
                map.put(bytes[i], 1);
            } else {
                map.put(bytes[i], count + 1);
            }
        }

        // 将 map转换成List 用于生成赫夫曼树
        List<HuffmanNode> nodes=new ArrayList<>();
        for(Map.Entry<Byte,Integer> entry: map.entrySet()){
            nodes.add(new HuffmanNode(entry.getKey(),entry.getValue()));
        }
        return nodes;
    }
}
